package com.leetcode.LC_MED;

public class LC34 {
    public int[] searchRange(int[] nums, int target) {

        if (nums.length == 0) {
            return new int[]{-1, -1};
        }

        int bin = toBin(nums, target);
        if (bin == -1) {
            return new int[]{-1, -1};
        }

        int a = bin, b = bin;
        while ((a >= 0&&nums[a] == target) || (b < nums.length && nums[b] == target)) {
            if (a >= 0 && nums[a] == target) {
                a--;
            }
            if (b < nums.length && nums[b] == target) {
                b++;
            }
        }
        return new int[]{a + 1, b - 1};

    }

    private int toBin(int[] nums, int target) {
        int a = 0, b = nums.length - 1;
        while (a <= b) {
            int mid = a + (b - a) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                b = mid - 1;
            } else if (nums[mid] < target) {
                a = mid + 1;
            }
        }
        return -1;
    }
}
